1. Field of the Invention
This invention relates generally to computer systems, and more particularly to a semaphore architecture for communicating between computer processes in a multiprogramming/multiprocessing environment.
2. Description of the Prior Art
Processing in first generation hardware/software computer systems was relatively straight-forward where the job of programming was considered to be the basic processing unit. For each user initiated job or transaction a program generally ran with little or not interruption until the job or transaction was completed. Many straight-forward jobs, such as the compilation and execution of a high level language program, such as Fortran, could and did run as a single process. More difficult jobs, however, would require multitask operations; and they would create other processes as they ran. (Note that a process is a concept implying the carrying on of some activity and should not be confused with the concept of a program, which is an activity description; and can be used by one or more processes. We can speak either of a process or a processor executing a program.)
The concept of a process as being the basic processing unit developed to fill a need for the multiprogramming/multiprocessing environment of third generation computers. In such an environment where many users are demanding service simultaneously, it is natural to conceive of multiple processes competing for resources within the computer system. Each process consists of a program (i.e., an ordered collection of instructions and other data associated with the instructions) which is executed by the computer, and operates on data to perform a user's job, or some phase of that job. Where many such processes are demanding simultaneous attention from the system, the task of communicating with and between such processes and the task of controlling and allocating resources to such processes, particularly in view of the requirements of fourth generation systems becomes extremely complex.
In a multiprogramming/multiprocessing environment, it is essential that cooperation between two or more sequential processes be efficiently and expeditiously realized. While many solutions to this problem have been proposed in the past, the technique of process communication and control needed for the fourth generation computers germinated in the concepts developed by E. W. Dijkstra in a paper entitled "Cooperative Sequential Processes from Programming Languages", NATO Advanced Study Institute, edited by F. Jenuys of Paris, and published in Academic Press in 1968. In this paper Dijkstra postulates a basic concept of a semaphore for use in proces synchronization and P and V instructions operating upon the semaphore. Unfortunately, Dijkstra provides for process communication and process synchronization solely by software usage, thus not only slowing down the operating time of the system, but also decreasing the efficiency and overall overhead required for such a system. More importantly, Dijkstra does not provide the concepts required for any significant exploitation of a fourth generation computer since he formulates only a basic premise in process synchronization. Moreover the concepts of P and V instructions expounded by Dijkstra are presented only in generalized terms and do not provide the system configuration needed in the fourth generation computer. Moreover, Dijkstra merely provides a software basis for interpreting and using P and V instructions. Accordingly where a process was designed to perform one of these P or V operations, it would evoke an operating system routine to perform it. The operating system routine would frequently have to run with interrupts inhibited to prevent other processes from gaining control of the processor while it is manipulating the semaphore. The operating system subroutine then does the incrementing and decrementing of the semaphore, as the case may be, and if necessary manipulates the process queues. After it has completed all these operations, it once again enables interrupts and returns to the evoking process.
In later work the P and V operations were implemented in firmware. (See patents incorporated by reference herein.) The difficulty here is that the firmware is now made aware of the data structures used to implement the concept of a process and to manage process queues. This means that for practical purposes the software cannot change the topology of these structures once the firmware has been implemented and these structures designed into the system. This is a very rigid position for the software where it is preferable to be able to change these structures due to changing needs, such as use of alternate queueing for new algorithms.
What was needed, therefore, was a method and apparatus for coordinating and communicating with processes that has the advantages of the P and V operations implemented in software, as well as those implemented in firmware, without the attendant disadvantages of each.